package com.leetcodehot.problems;

import java.util.Arrays;

public class problems1385 {
    /**
     * 给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
     * <p>
     * 「距离值」 定义为符合此距离要求的元素数目：
     * 对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
     */
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int n = arr2.length;
        int left;
        int right;
        int res = 0;
        for (int i = 0; i < arr1.length; i++) {
            int x = arr1[i];
            //是否arr2的所有元素与x的距离都大于d
            if (x < arr2[0] - d && x > d + arr2[n - 1]) {
                res++;
                continue;
            }
            left = -1;
            right = n;
            while (left + 1 < right) {
                //查找x应该插入的位置
                int mid = left + (right - left) / 2;
                if (arr2[mid] < x) {
                    left = mid;
                } else {
                    right = mid;
                }
            }//right是x应该插入的下标
            if (right == 0 || right == n) {
                if (right == n) {
                    if (x - arr2[n - 1] > d) {
                        res++;
                    }
                }
                if (right == 0) {
                    if (arr2[0] - x > d) {
                        res++;
                    }
                }
                continue;
            }
            if (Math.abs(x - arr2[right - 1]) > d && Math.abs(x - arr2[right]) > d) {
                res++;
            }
        }
        return res;
    }
}
